package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-02
 * Time:16:35
 */

/**
 *
 牛客算法篇:BM30 二叉搜索树与双向链表
 描述
 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
 数据范围：输入二叉树的节点数 0≤n≤10000≤n≤1000，二叉树中每个节点的值 0≤val≤10000≤val≤1000
 要求：空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)
 注意:
 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
 2.返回链表中的第一个节点的指针
 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
 4.你不用输出双向链表，程序会根据你的返回值自动打印输出
 输入描述：
 二叉树的根节点
 返回值描述：
 双向链表的其中一个头节点。
 示例1
 输入：
 {10,6,14,4,8,12,16}
 返回值：
 From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
 说明：
 输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
 */
public class Convert {
    public static void main(String[] args) {
        TreeNode a = new TreeNode(10);
        TreeNode b = new TreeNode(6);
        TreeNode c = new TreeNode(14);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(8);
        TreeNode f = new TreeNode(12);
        TreeNode g = new TreeNode(16);

        a.left = b;a.right = c;
        b.left = d;b.right = e;
        c.left = f;c.right = g;
        Convert(a);
    }
//    static TreeNode output;
//    static TreeNode cur = new TreeNode(0);
//    static int[] num = new int[100];
//    static int index = 0;
//    public static TreeNode Convert(TreeNode pRootOfTree) {
//        output = new TreeNode(0);
//        output.right = cur;
//        cur = new TreeNode(0);
//        Sequencetraversal(pRootOfTree);
//        BuidNewTree(num);
//        output = output.right;
//        output.left = null;
//        return output;
//    }
//    public static void Sequencetraversal(TreeNode root) {
//        if(root == null) return;
//        Sequencetraversal(root.left);
//        num[index++] = root.val;
//        Sequencetraversal(root.right);
//    }
//
//    public static void BuidNewTree(int[] num) {
//        cur.val = num[0];
//        for(int i = 1;i < index;i++){
//            TreeNode tmp = new TreeNode(num[i]);
//            cur.right = tmp;
//            tmp.left = cur;
//            cur = tmp;
//        }
//    }
    public static TreeNode Convert(TreeNode root) {
        if (root == null)
            return null;
        if (root.left == null && root.right == null)
            return root;
        // 1.将左子树构造成双链表，并返回链表头节点
        TreeNode left = Convert(root.left);
        TreeNode p = left;
        // 2.定位至左子树双链表最后一个节点
        while (p != null && p.right != null) {
            p = p.right;
        }
        // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
        if (left != null) {
            p.right = root;
            root.left = p;
        }
        // 4.将右子树构造成双链表，并返回链表头节点
        TreeNode right = Convert(root.right);
        // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
        if (right != null) {
            right.left = root;
            root.right = right;
        }
        return left != null ? left : root;
    }
}
